package service.week01.leetcode.editor.cn;
//给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 
//
// 
//上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。 
//
// 
//
// 示例： 
//
// 
//给定 matrix = [
//  [3, 0, 1, 4, 2],
//  [5, 6, 3, 2, 1],
//  [1, 2, 0, 1, 5],
//  [4, 1, 0, 1, 7],
//  [1, 0, 3, 0, 5]
//]
//
//sumRegion(2, 1, 4, 3) -> 8
//sumRegion(1, 1, 2, 2) -> 11
//sumRegion(1, 2, 2, 4) -> 12
// 
//
// 
//
// 提示： 
//
// 
// 你可以假设矩阵不可变。 
// 会多次调用 sumRegion 方法。 
// 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。 
// 
// Related Topics 动态规划 
// 👍 277 👎 0

public class P304RangeSumQuery2dImmutable {
    public static void main(String[] args) {
//        NumMatrix solution = new P304RangeSumQuery2dImmutable().new NumMatrix();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class NumMatrix {

        private int[][] sum;

        public NumMatrix(int[][] matrix) {
            sum = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    sum[i][j] = getSum(i - 1, j) + getSum(i, j - 1) - getSum(i - 1, j - 1) +
                            matrix[i][j];
                }
            }
        }


        public int sumRegion(int row1, int col1, int row2, int col2) {
            //二维前缀和公式
            return getSum(row2, col2) - getSum(row1 - 1, col2)
                    - getSum(row2, col1 - 1) + getSum(row1 - 1, col1 - 1);
        }

        /**
         * 防止数组越界
         *
         * @param i
         * @param j
         * @return
         */
        private int getSum(int i, int j) {
            if (i > 0 && j > 0) {
                return sum[i][j];
            } else {
                return 0;
            }
        }


    }

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
//leetcode submit region end(Prohibit modification and deletion)

}